//============================================================================
// Name        : singly_linked_list.cpp
// Author      : jiangkai
// Version     :
// Description : singly_linked_list
//============================================================================
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

typedef struct node
{
	int x;
	struct node* next;
}Node;

Node* newnode(int a)
{
	Node* p=(Node*) malloc (sizeof(Node));
	if (!p)
	{
		printf("the memory is full\n");
	}
	p->x=a;
	p->next=NULL;
	return p;
}


Node* build()
{
	Node* first=NULL;
	Node* r=NULL;
	Node* p;
	char c;
	int data;
	printf("Another element? y or n\n");
	while ((c=getchar()) == '\n');
	while (tolower(c) != 'n')
	{
		scanf("%d",&data);
		p=newnode(data);
		if ( first != NULL )
			r->next=p;
		else
			first=p;
		r=p;
		printf("Another element? y or n\n");
		while ((c=getchar()) == '\n' );
	}
	return first;
}

void insert(int nth,int x,Node* first)
{
	int cnt=1;
	Node *p;
	Node *q;
	p=first;
	q=newnode(x);
	while (p != NULL )
	{
		if ( cnt == nth )
		{
			q->next=p->next;
			p->next=q;
		}
		cnt++;
		p=p->next;
	}
}

void Delete_th(int n,Node* first)
{
	int cnt=1;
	Node *p;
	Node *q;
	q=first;
	//if (n == 1)
	//{
	  //  p=first->next;
	    //fi
	//}
    while ( q != NULL )
	{
		if ( cnt == n-1 )
		{
			p=q->next;
            q->next=p->next;
			free(p);
		}
		cnt++;
		q=q->next;
	}
}

/*void Delete_element(int e,Node* first)
{
	Node *p,*q;
	p=first;
	while (p != NULL )
	{
		if (p->x == e)
		{
			q=p;
			q->next=p->next;
			free(p);
		}
		p=p->next;
	}
}*/


void find(int data,Node* first)
{
	Node *p;
	p=first;
	int cnt=1;
	int flag=0;
	while (p != NULL )
	{
		if ( data == p->x )
		{
			printf("%d is the %d",data,cnt);
			if (cnt % 10 == 1 && cnt % 100 != 11)
				cout<<"st";
			else if (cnt % 10 == 2 && cnt % 100 != 12)
				cout<<"nd";
			else if (cnt % 10 == 3 && cnt % 100 != 13)
				cout<<"rd";
			else
				cout<<"th";
			printf(" element.\n");
			flag=1;
		}
		cnt++;
		p=p->next;
	}
	if (flag == 0)
        printf("Not found the element.\n");
}

void modify(int nth,int data,Node* first)
{
    Node *p;
	p=first;
	int cnt=1;
	int flag=0;
	while (p != NULL )
	{
		if ( cnt == nth )
		{
			p->x=data;
			flag=1;
		}
		cnt++;
		p=p->next;
	}
	if (flag == 0)
        printf("Not found the element.\n");
}

void clear(Node* *first)
{
	Node* p=*first;
	while (*first)
	{
		p=(*first)->next;
		free(*first);
		*first=p;
	}
}

void print_list(Node* first)
{
	Node* r;
	r=first;
	if (r == NULL )
	{
	    printf("The list is empty.\n");
	    return;
	}
	else
	{
        printf("%d",r->x);
        r=r->next;
	}
	while (r != NULL )
	{
		printf(" -> ");
		printf("%d",r->x);
		r=r->next;
	}
	cout<<endl;
}

int main() {
    //freopen("in.txt","r",stdin);
    int test,nth;
	Node* top;
	top=build();          // create new list
	print_list(top);
	cin>>test;
	find(test,top);       //found what i th element is
	int number,ith;
	scanf("%d%d",&ith,&number);
    insert(ith,number,top);    //insert element after i th
    print_list(top);
    modify(4,99,top);        //turn 2nd element to 1000
    print_list(top);
    cout<<"delete the nth element"<<endl;
	cin>>nth;
	Delete_th(nth,top);
	print_list(top);
	Node** p=&top;
	clear(p);             // empty the list
	print_list(top);
	return 0;
}
